package string.滑动窗口;

import java.util.HashMap;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最小覆盖子串76.java
 * @createTime 2022年07月26日 22:33:00
 */
public class 最小覆盖子串76 {
	public static String minWindow(String s, String t) {
		//滑动窗口符合条件字符的统计情况
		HashMap<Character, Integer> window = new HashMap<>();
		//定义需要寻找的字符和对应的字符个数
		HashMap<Character, Integer> target = new HashMap<>();
		for (char c : t.toCharArray()) {
			target.put(c, target.getOrDefault(c, 0) + 1);
		}
		//窗口的起点和结束
		int left = 0; //窗口开始位置
		int right = 0; //窗口结束位置
		int valid = 0; //字符出现的次数都满足的数量，比如t中字符a出现3次，那么s中出现3次，valid才+1
		int strLength = Integer.MAX_VALUE; //字符长度
		int start = 0;

		//先遍历到窗口的右侧包含所有的字符
		while (right < s.length()) {
			//当前遍历到的字符
			char c1 = s.charAt(right);
			//推动窗口的右边界
			right++;
			//如果是目标字符则要统计起来
			if (target.containsKey(c1)) {
				window.put(c1, window.getOrDefault(c1, 0) + 1);
				if (window.get(c1).equals(target.get(c1))) {
					valid++;
				}
			}
			System.out.println(window);
			//当字符出现的次数都满足的时候，说明窗口已经符合要求了，可以进行收缩。
			while (valid == target.size()) {
				//如果长度有效
				if (right - left < strLength) {
					start = left;
					strLength = right - left;
				}
				char c2 = s.charAt(left);
				//左边窗口进行收缩
				left++;
				//如果是目标字段，需要进行移除
				if (target.containsKey(c2)) {
					//如果此时的目标字段个数和遍历结果的个数一样，去除的时候需要把有效个数减一
					if (target.get(c2).equals(window.get(c2))) {
						valid--;
					}
					window.put(c2, window.get(c2) - 1);
				}
			}
		}
		return strLength == Integer.MAX_VALUE ? "" : s.substring(start, start + strLength);
	}
}
